﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0173_MyLinkedList : IAlgorithm
    {
        // 707. 设计链表

        // 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

        // 在链表类中实现这些功能：
        //  get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
        //  addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
        //  addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
        //  addAtIndex(index, val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
        //  deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

        // 提示：
        //  所有val值都在[1, 1000] 之内。
        //  操作次数将在[1, 1000] 之内。
        //  请不要使用内置的 LinkedList 库。

        public void Test()
        {
        }

        // 算法
        // 单链表
        public class MyLinkedList
        {
            int size;
            ListNode head;
            public MyLinkedList()
            {
                size = 0;
                head = new ListNode();
            }

            public int Get(int index)
            {
                if (index < 0 || index >= size) return -1;
                ListNode curr = head;
                for (int i = 0; i < index + 1; ++i) curr = curr.next;
                return curr.val;
            }

            public void AddAtHead(int val)
            {
                AddAtIndex(0, val);
            }

            public void AddAtTail(int val)
            {
                AddAtIndex(size, val);
            }

            public void AddAtIndex(int index, int val)
            {
                if (index > size) return;
                if (index < 0) index = 0;
                size++;
                ListNode pred = head;
                for (int i = 0; i < index; ++i) pred = pred.next;
                ListNode toAdd = new ListNode(val);
                toAdd.next = pred.next;
                pred.next = toAdd;
            }

            public void DeleteAtIndex(int index)
            {
                if (index < 0 || index >= size) return;
                size--;
                ListNode pred = head;
                for (int i = 0; i < index; ++i) pred = pred.next;
                pred.next = pred.next.next;
            }
        }

        public class ListNode1
        {
            public int val;
            public ListNode1 next;
            public ListNode1 prev;
            public ListNode1(int x) { val = x; }
        }

        public class MyLinkedList1
        {
            int size;
            ListNode1 head, tail;
            public MyLinkedList1()
            {
                size = 0;
                head = new ListNode1(0);
                tail = new ListNode1(0);
                head.next = tail;
                tail.prev = head;
            }

            public int get(int index)
            {
                if (index < 0 || index >= size) return -1;

                ListNode1 curr = head;
                if (index + 1 < size - index)
                    for (int i = 0; i < index + 1; ++i) curr = curr.next;
                else
                {
                    curr = tail;
                    for (int i = 0; i < size - index; ++i) curr = curr.prev;
                }

                return curr.val;
            }

            public void addAtHead(int val)
            {
                ListNode1 pred = head, succ = head.next;

                ++size;
                ListNode1 toAdd = new ListNode1(val);
                toAdd.prev = pred;
                toAdd.next = succ;
                pred.next = toAdd;
                succ.prev = toAdd;
            }

            /** Append a node of value val to the last element of the linked list. */
            public void addAtTail(int val)
            {
                ListNode1 succ = tail, pred = tail.prev;

                ++size;
                ListNode1 toAdd = new ListNode1(val);
                toAdd.prev = pred;
                toAdd.next = succ;
                pred.next = toAdd;
                succ.prev = toAdd;
            }

            public void addAtIndex(int index, int val)
            {
                if (index > size) return;

                if (index < 0) index = 0;

                ListNode1 pred, succ;
                if (index < size - index)
                {
                    pred = head;
                    for (int i = 0; i < index; ++i) pred = pred.next;
                    succ = pred.next;
                }
                else
                {
                    succ = tail;
                    for (int i = 0; i < size - index; ++i) succ = succ.prev;
                    pred = succ.prev;
                }

                ++size;
                ListNode1 toAdd = new ListNode1(val);
                toAdd.prev = pred;
                toAdd.next = succ;
                pred.next = toAdd;
                succ.prev = toAdd;
            }

            public void deleteAtIndex(int index)
            {
                if (index < 0 || index >= size) return;

                ListNode1 pred, succ;
                if (index < size - index)
                {
                    pred = head;
                    for (int i = 0; i < index; ++i) pred = pred.next;
                    succ = pred.next.next;
                }
                else
                {
                    succ = tail;
                    for (int i = 0; i < size - index - 1; ++i) succ = succ.prev;
                    pred = succ.prev.prev;
                }

                --size;
                pred.next = succ;
                succ.prev = pred;
            }
        }
    }
}
